class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();
        int begin = 0;
        while(left < right)
        {
            if(nums[nums.size()-1] >= nums[0])
                break;
            if(left>0 && nums[left]<nums[left-1])
            {
                begin = left;
                break;
            }
            int mid = (left + right) / 2;
            if(nums[mid] < nums[mid-1])
            {
                begin = mid;
                break;
            }
            if(nums[mid] < nums[left])
                right = mid;
            else if(nums[mid] > nums[right-1])
                left = mid + 1;
        }
        
        int first = 0;
        int last = 0;
        if(nums[nums.size()-1] >= target)
        {
            first = begin;
            last = nums.size();
        }
        else
        {
            first = 0;
            last = begin;
        }

        int res = -1;
        while(first < last)
        {
            int mid = (first + last) / 2;
            if(nums[mid] > target)
                last = mid;
            else if(nums[mid] < target)
                first = mid + 1;
            else
                return mid;
        }

        return res;
    }
};